package com.java.comprehensive.arithmetic.leecode.tags.linkedlist;

import util.ListNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.Stack;

/**
 * @Author: 窦绍飞
 * @Date: 2022/7/12
 */
public class LeetCode_234 {
	static Set<ListNode> set;

	public static boolean isPalindrome(ListNode head) {

		if (head == null || head.next == null) return true;

		ListNode curr = head, pre = null;

		while (curr.next != null) {
			pre = curr;
			curr = curr.next;
		}
		if (head.val != curr.val) return false;
		pre.next = null;
		return isPalindrome(head.next);
	}

	public static boolean isPalindromeTwo(ListNode head) {
		List<Integer> list = new ArrayList<>();

		ListNode curr = head;
		while (curr.next != null) {
			list.add(curr.val);
			curr = curr.next;
		}
		list.add(curr.val);

		int j = list.size() - 1;
		for (int i = 0; i < list.size(); i++) {
			if (!list.get(i).equals(list.get(j))) return false;
			j--;
		}
		return true;
	}

	public static boolean isPalindromeThree(ListNode head) {
		Stack<Integer> stack = new Stack<>();

		ListNode curr = head;
		while (curr.next != null) {
			stack.push(curr.val);
			curr = curr.next;
		}
		stack.push(curr.val);

		while (head != null) {
			Integer pop = stack.pop();
			if (!pop.equals(head.val)) {
				return false;
			}
			head = head.next;
		}
		return true;
	}

	/**
	 * 先找到中心节点 ，再将另一半翻转 1-1 对比
	 *
	 * @param head
	 * @return
	 */
	public static boolean isPalindromeFour(ListNode head) {
		if (head == null || head.next == null) return true;

		//找到中心节点
		ListNode fast = head, slow = head, pre = null;
		while (fast != null && fast.next != null) {
			//快指针走两步 满指针走一步 就是找到中间节点了
			fast = fast.next.next;
			pre = slow;
			slow = slow.next;
		}

		if (fast == null) {
			//偶数个节点
			pre.next = null;
			slow = reverse(slow);

			while (head != null) {
				if (head.val != slow.val) {
					return false;
				}
				head = head.next;
				slow = slow.next;
			}
		} else {
			pre.next = null;
			ListNode next = slow.next;

			slow.next = null;

			next = reverse(next);
			while (head != null) {
				if (head.val != next.val) {
					return false;
				}
				head = head.next;
				next = next.next;
			}
		}
		return true;
	}

	private static ListNode reverse(ListNode node) {
		ListNode pre = null, curr = node;
		while (curr != null) {
			// 1 --- 2,3,4
			// 2 -- 3,4
			ListNode next = curr.next;
			// 1 --null
			// 2 ->1 --null
			curr.next = pre;
			// 1
			// 2->1->null
			pre = curr;
			//2,3,4
			// 3,4
			curr = next;
		}
		return pre;
	}

	public static void main(String[] args) {
		ListNode listNode4 = new ListNode(1, null);
		ListNode listNode3 = new ListNode(2, listNode4);
		ListNode listNode2 = new ListNode(2, listNode3);
		ListNode listNode1 = new ListNode(1, listNode2);
		System.out.println(isPalindromeFour(listNode1));

	}

}
